package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Scanner;

/*
数字三角形(POJ1163)

在数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。
路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。

三角形的行数大于1小于等于100，数字为 0 - 99

输入格式：
//5表示三角形的行数,接下来输入三角形
in
5		
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

out
30

要求输出最大和
 */

public class h数字三角形最大路径值byDFS {
	public static void main(String[] args) {
		h数字三角形最大路径值byDFS test = new h数字三角形最大路径值byDFS();
		test.useDFS();
	}
	
	/**
	 * 前置方法
	 */
	public void useDFS() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[][] triangle = new int[N][];
		for (int i = 0; i < N; i++) {
			triangle[i] = new int[i + 1];
			for (int j = 0; j < i + 1; j++) {
				triangle[i][j] = scanner.nextInt();
			}
		}
		int res = DFS(N, triangle, 0, 0);
		System.out.println(res);
	}
	
	/**
	 * O(2^N)
	 * 递归形式
	 * 因为没有改变状态
	 * 也没有公共的可改变的变量
	 * 所以不用回溯
	 * @param N
	 * @param triangle
	 * @param row
	 * @param col
	 * @return
	 */
	public int DFS(int N, int[][] triangle, int row, int col) {
		if (row == N - 1) {//如果递归到最后一层，直接输出该元素；递归出口
			return triangle[row][col];
		} else {
			int left = DFS(N, triangle, row + 1, col);//此节点的左孩子的最大路径值
			int right = DFS(N, triangle, row + 1, col + 1);//此节点的右孩子的最大路径值
			int max = Math.max(left, right);//取它们最大的
			return max + triangle[row][col];//此节点数值 + 它们最大的
		}
	}
}
